package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.ListNode;
import org.springframework.util.Assert;

import java.util.Queue;

/**
 * @ClassName PalindromeLinkedList
 * @Description PalindromeLinkedList
 * @Author wanghaiwei
 * @Date 2023/1/16 13:50
 */
public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        //参考
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //基数个的时候，slow正好指向中间那个节点，需要向右挪一个，才是指向右半部分链表的"头"
        if (fast != null) {
            slow = slow.next;
        }
        //反转右半部分节点
        ListNode preForRightPart = null;
        while(slow != null) {
            ListNode tmp = slow.next;
            slow.next = preForRightPart;
            preForRightPart = slow;
            slow = tmp;
        }
        //开始左右两段匹配
        while (head != null && preForRightPart != null) {
            if(head.val != preForRightPart.val) {
                return false;
            }
            head = head.next;
            preForRightPart = preForRightPart.next;
        }
        return true;
    }

    public static void main(String[] args) {
        PalindromeLinkedList solution = new PalindromeLinkedList();
        Assert.isTrue(solution.isPalindrome(ListNode.convertArrayToListNode(new int[]{1,2,2,1})), "1,2,2,1计算错误，预期:true,实际false");
        Assert.isTrue(!solution.isPalindrome(ListNode.convertArrayToListNode(new int[]{1,2,3,1})), "1,2,3,1计算错误，预期:false,实际true");
        Assert.isTrue(solution.isPalindrome(ListNode.convertArrayToListNode(new int[]{1,2,4,2,1})), "1,2,4,2,1计算错误，预期:true,实际false");

    }
}
